package DynamicProgramingSeries;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreakSolution_139 {
    public boolean wordBreak_1(String s, List<String> wordDict) {
        // 完全背包问题
        // dp[i] = 字符串s前i个字符组成的字符串s[0..i−1]是否能被空格拆分成若干个字典中出现的单词
        Set<String> wordDictSet = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length()+1];

        dp[0] = true;

        for(int i = 1; i<=s.length(); i++){
            for(int j=0; j<i; j++){
                // wordDict存在s.substring(j, i)这个单词
                if(dp[j] && wordDictSet.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }


    public boolean wordBreak_2(String s, List<String> wordDict) {
        // 完全背包问题
        // dp[s] = 用单词列表拼成字符串s，是否可行
        boolean[] dp = new boolean[s.length() + 1];

        dp[0] = true;

        // 背包容量
        for (int i = 1; i <= s.length(); i++) {
            for (String word : wordDict) {
                int len = word.length();
                // 1、背包容量i能放下word
                // 2、用单词列表拼成字符串i-len，是否可行
                // 3、是否有word符合条件
                if (i >= len && dp[i - len] && word.equals(s.substring(i - len, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }
}
